package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 142. 环形链表 II
 * @date 2025/1/21 13:33
 */
public class E142 {

    /**
     * <h3>快慢指针</h3>
     *
     * @param head 头节点
     * @return 环形链表入口节点
     */
    public ListNode detectCycle(ListNode head) {
        ListNode rabbit = head;
        ListNode tortoise = head;
        while (rabbit != null && rabbit.next != null) {
            rabbit = rabbit.next.next;
            tortoise = tortoise.next;
            if (tortoise == rabbit) {
                rabbit = head;
                while (rabbit != tortoise) {
                    rabbit = rabbit.next;
                    tortoise = tortoise.next;
                }
                return rabbit;
            }
        }
        return null;
    }
}
